def dp(input):
    l = len(input)
    m = {}
    res = ""
    for i in range(l - 1, -1, -1):
    # for i in range(0, l):
        for j in range(i, l):
            if i == j:
                m[(i, j)] = True
            elif j - i == 1:
                m[(i, j)] = input[i] == input[j]
            else:
                m[(i, j)] = m[(i + 1, j - 1)] and input[i] == input[j]

            if m[(i, j)] and j - i + 1 > len(res):
                res = input[i:j + 1]
    return res


print(dp("babad"))
print(dp("aaaaaabbbb"))
